/**
 * @author kris
 * 
 */
public class Percolation {

	private enum SiteIs {
		BLOCKED, OPEN;
	}

	private WeightedQuickUnionUF grid;
	private SiteIs[] sites;
	private int topVirtualNode;
	private int bottomVirtualNode;
	private int N;

	/**
	 * create N-by-N grid, with all sites blocked
	 * 
	 * @param N
	 * @throws IOException
	 */
	public Percolation(int N) {
		this.N = N;

		sites = new SiteIs[N * N];
		for (int i = 0; i < sites.length; i++) {
			sites[i] = SiteIs.BLOCKED;
		}
		topVirtualNode = 0;
		bottomVirtualNode = N * N + 1;
		grid = new WeightedQuickUnionUF(N * N + 2);
	}

	/**
	 * open site (row i, column j) if it is not already.
	 * 
	 * @param i
	 * @param j
	 */
	public void open(int i, int j) {

		int index = getIndex(i - 1, j - 1);

		if (sites[index] == SiteIs.OPEN) {
			return;
		}

		sites[index] = SiteIs.OPEN;

		int gridIndex = index + 1;
		int northIndex = getNorthIndex(i - 1, j - 1);
		int eastIndex = getEastIndex(i - 1, j - 1);
		int southIndex = getSouthIndex(i - 1, j - 1);
		int westIndex = getWestIndex(i - 1, j - 1);

		if (northIndex == -1) {
			grid.union(gridIndex, topVirtualNode);
		} else if (sites[northIndex] == SiteIs.OPEN) {
			grid.union(gridIndex, northIndex + 1);
		}
		if (eastIndex != -1 && sites[eastIndex] == SiteIs.OPEN) {
			grid.union(gridIndex, eastIndex + 1);
		}
		if (westIndex != -1 && sites[westIndex] == SiteIs.OPEN) {
			grid.union(gridIndex, westIndex + 1);
		}
		if (southIndex == -1) {
			grid.union(gridIndex, bottomVirtualNode);
		} else if (sites[southIndex] == SiteIs.OPEN) {
			grid.union(gridIndex, southIndex + 1);
		}
	}

	private int getWestIndex(int row, int column) {
		if (column == 0) {
			return -1;
		}
		int index = (row * N) + (column - 1);
		return index;
	}

	private int getSouthIndex(int row, int column) {
		if (row == N - 1) {
			return -1;
		}
		int index = ((row + 1) * N) + column;
		return index;
	}

	private int getEastIndex(int row, int column) {
		if (column == N - 1) {
			return -1;
		}
		int index = row * N + (column + 1);
		return index;
	}

	private int getNorthIndex(int row, int column) {
		if (row == 0) {
			return -1;
		}
		int index = ((row - 1) * N) + column;
		return index;
	}

	private int getIndex(int row, int column) {
		validate(row, column);
		int index = row * N + column;
		return index;
	}

	private void validate(int i, int j) {
		if (i < 0 || i > N || j < 0 || j > N) {
			throw new IndexOutOfBoundsException();
		}
	}

	/**
	 * is site (row i, column j) open?
	 * 
	 * @param i
	 * @param j
	 * @return
	 */
	public boolean isOpen(int i, int j) {
		int index = getIndex(i - 1, j - 1);
		return sites[index] == SiteIs.OPEN;
	}

	/**
	 * is site (row i, column j) full?
	 * 
	 * @param i
	 * @param j
	 * @return
	 */
	public boolean isFull(int i, int j) {
		int gridIdex = getIndex(i - 1, j - 1) + 1;
		return grid.connected(gridIdex, topVirtualNode);
	}

	/**
	 * does the system percolate?
	 * 
	 * @return
	 */
	public boolean percolates() {
		return grid.connected(bottomVirtualNode, topVirtualNode);
	}

}
